package Stack.Medium;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 这道题的实现全部参考了@windliang的题解
 */
public class LC0155 {
    /**
     * 思路一：用第二个栈保存栈中元素的“若干最小值”。具体来说，当进入栈1元素的元素比栈2顶部元素大时，不做任何操作；小于或等于栈2顶部元素时，将该
     * 元素同时加入栈2。第一个压栈的元素始终要加入栈2。出栈1时，如果元素不等于栈2顶部元素，则不做任何操作，否则将栈2顶部元素出栈。这种解法的原理
     * 在于，栈2相当于只保存了栈1的部分元素，且这些元素从底到顶是递减的；此外，栈2两个元素a,b之间省略掉的那些元素，一定会比a和b都更大。
     */
    class MinStack1 {
        Deque<Integer> stack = new LinkedList<>();
        Deque<Integer> minStack = new LinkedList<>();

        public MinStack1() {

        }

        public void push(int val) {
            if (stack.isEmpty()) {
                minStack.push(val);
            }
            else if (val <= minStack.peek()) minStack.push(val);
            stack.push(val);
        }

        public void pop() {
            int popped = stack.pop();
            if (popped == minStack.peek()) minStack.pop();
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }
}
